package two.chapter_3.c3_1;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_1.c1_3.CollectionEmptyException;
import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;

/**
 * 顺序查找的无序符号表
 * 使用链表数据结构
 */
public class SequentialSearchST<Key, Value> implements ST<Key, Value> {
    private Node head;
    private int size;

    @Override
    public void put(Key key, Value value) {


            for (Node node = head; node != null; node = node.next) {
                if (node.key.equals(key)) {
                    node.value = value;//已经存在相同key的元素
                    return;
                }
            }
            Node node = new Node(key, value);
            node.next = head;
            head = node;

            size++;
    }

    @Override
    public Value get(Key key) {

        for (Node node=head;node!=null;node=node.next){
            if (node.key.equals(key)){
                return node.value;
            }
        }

        return null;
    }

    @Override
    public void delete(Key key) {

       head=delete(head,key);

    }

    private Node delete(Node node, Key key) {

        if (node.key.equals(key)){
            size--;
            return node.next;
        }
        node.next=delete(node,key);

        return node;
    }

    public void myDelete(Key key){
        if (isEmpty()){
            throw new CollectionEmptyException();
        }
        if (head.key.equals(key)){
            head=head.next;
            size--;

        }else {
            for (Node node=head;node.next!=null;node=node.next){
                if (node.next.key.equals(key)){
                    node.next=node.next.next;
                    node.next.next=null;
                    size--;
                    return;
                }
            }
        }

    }

    @Override
    public boolean contains(Key key) {
        for (Node node=head;node!=null;node=node.next){
            if (node.key.equals(key)){
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean isEmpty() {
        return size()==0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterable<Key> keys() {
        Queue<Key> queue=new LinkedQueue<>();
        for (Node node=head;node!=null;node=node.next){
            queue.enqueue(node.key);
        }


        return queue;
    }

    private class Node {
        Key key;
        Value value;
        Node next;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
        }

    }
}
